#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>
#include<stdlib.h>


#include "algraph.h"
#include "stack.h"


int TopologicalOrder(ALGraph G,SqStack &T);

int LocateVex(ALGraph &G,char v)
{
	int i;
	for(i=0;i<G.vexnum;i++)
	{
		if(v==G.vertices[i].data) 
			return i;
	}
	exit(0);
}

void CreateALG(ALGraph &G)
{
	int i,k,j,w;
	char v1,v2;
	ArcNodeList p;
	ArcNodeList q[MAX_VERTEX_NUM]; 
	//ArcNodeList* q=new ArcNodeList[MAX_VERTEX_NUM]; 



	printf("please input G.vextexnum:");
	fflush(stdin);
	scanf("%d",&G.vexnum);
	fflush(stdin);
	printf("please input G.arcnum:");	
	scanf("%d",&G.arcnum);
	fflush(stdin);
	printf("please input G.vextex:");
	for (i=0;i<G.vexnum;++i)
	{
		G.vertices[i].data=getchar();
		G.vertices[i].firstarc=(ArcNodeList)malloc(sizeof(ArcNode));
		G.vertices[i].firstarc->nextarc=NULL;
		q[i]=G.vertices[i].firstarc;
	}

	for(k=0;k<G.arcnum;k++)
	{
		printf("please input <v1 v2>:");
		fflush(stdin);
		scanf("%c%c %d",&v1,&v2,&w);
		i=LocateVex(G,v1);
		j=LocateVex(G,v2);
		p=(ArcNodeList)malloc(sizeof(ArcNode));
		p->adjvex=j;
		p->info=w;
		p->nextarc=q[i]->nextarc;
		q[i]->nextarc=p;	
		q[i]=p;

	}
}

void FindInDegree(ALGraph G,int *indegree)
{
	int i,j,count;
	struct ArcNode *p;
	for (i=0;i<G.vexnum;i++)
	{
		count=0;
		for (j=0;j<G.vexnum;j++)
		{
			for (p=G.vertices[j].firstarc->nextarc;p;p=p->nextarc)
			{
				if (p->adjvex==i)
				{
					count++;
				}	
			}
		}
		indegree[i]=count;
	}
}
//
//void FindOutDegree(ALGraph G,int *indegree)
//{
//	int i,count;
//	struct ArcNode *p;
//	for (i=0;i<G.vexnum;i++)
//	{
//		count=0;
//		for (p=G.vertices[i].firstarc->nextarc;p;p=p->nextarc)
//			{
//				count++;	
//			}
//		indegree[i]=count;
//	}
//}


int TopologicalSort(ALGraph G)
{
	int indegree[MAX_VERTEX_NUM]={0};
	int i,count=0,k;
	SqStack S;
	struct ArcNode *p;
	FindInDegree(G,indegree);
	InitStack(S);
	for (i=0;i<G.vexnum;++i)
	{
		if (!indegree[i])
		{
			Push(S,i);
		}
	}
	while (!StackEmpty(S))
	{
		Pop(S,i);
		printf("%d%c ",i,G.vertices[i].data);
		++count;
		for (p=G.vertices[i].firstarc->nextarc;p;p=p->nextarc)
		{
			k=p->adjvex;
			if (!(--indegree[k]))
			{
				Push(S,k);
			}
		}
	}
	if (count<G.vexnum)
	{
		return 0;
	}
	else
	{
		return 1;
	}
}
int ve[MAX_VERTEX_NUM]={0};

int TopologicalOrder(ALGraph G,SqStack &T)
{
	int indegree[MAX_VERTEX_NUM]={0};
	int i,count=0,j,k;
	SqStack S;
	struct ArcNode *p;
	FindInDegree(G,indegree);
	InitStack(S);
	for (i=0;i<G.vexnum;++i)
	{
		if (!indegree[i])
		{
			Push(S,i);
		}
	}
	InitStack(T);
	while (!StackEmpty(S))
	{
		Pop(S,j);
		Push(T,j);
		++count;
		for (p=G.vertices[j].firstarc->nextarc;p;p=p->nextarc)
		{
			k=p->adjvex;
			if (--indegree[k]==0)
			{
				Push(S,k);
			}
			if (ve[j]+p->info>ve[k])
			{
				ve[k]=ve[j]+p->info;
			}
		}
	}
	if (count<G.vexnum)
	{
		return 0;
	}
	else
	{
		return 1;
	}
}
int  CriticalPath(ALGraph G)
{
	SqStack T;
	if (!TopologicalOrder(G,T))
	{
		return 0;
	}
	int vl[MAX_VERTEX_NUM];
	int i,j,k,dut,ee,el;
	struct ArcNode *p;
	char tag;
	for (i=0;i<G.vexnum;++i)
	{
		vl[i]=ve[G.vexnum-1];
	}
	while (!StackEmpty(T))
	{
		for (Pop(T,j),p=G.vertices[j].firstarc->nextarc;p;p=p->nextarc)
		{
			k=p->adjvex;
			dut=p->info;
			if (vl[k]-dut<vl[j])
			{
				vl[j]=vl[k]-dut;
			}
		}
	}
	for (j=0;j<G.vexnum;++j)
	{
		for (p=G.vertices[j].firstarc->nextarc;p;p=p->nextarc)
		{
			k=p->adjvex;
			dut=p->info;
			ee=ve[j];
			el=vl[k]-dut;
			tag=(ee==el)?'*':' ';
			if (tag=='*')
			{
				printf("%d,%d,%d,%d,%d %c ",j,k,dut,ee,el,tag);
			}
		}
	}
	return 1;
}